# -*- encoding: utf-8 -*-
"""
利用分治算法求一组数据中，两个的相邻元素相加后结果最大的值
"""


def max_subarray_sum(array, left, right):
    if left >= right:
        return array[right]
    mid = (right + left) // 2
    left_half_max = max_subarray_sum(array, left, mid)
    right_half_max = max_subarray_sum(array, mid + 1, right)
    return max(left_half_max, right_half_max)


if __name__ == '__main__':
    array = [-2, -5, 6, -2, -3, 1, 5, -6]
    array_length = len(array)
    print("Maximum sum of contiguous subarray:", max_subarray_sum(array, 0, array_length - 1))
